package cn.sjtu.algorithm.string;

import java.util.Arrays;

public class KMP {
    public static void main(String[] args) {
        int[] next = next("aabaaf");
        System.out.println(Arrays.toString(next));
        System.out.println(KMP("aabaabaa", "aabaaf"));
    }

    /**
     * 获取模式串的Next数组
     * @param pattern 模式串
     * @return next数组
     */
    public static int[] next(String pattern) {
        int n = pattern.length();

        // 1. next数组的含义是Next[i]是下标为i的位置发生不匹配时，从[0, i - 1]的子字符串的最长相等前后缀
        int[] next = new int[n];

        // 2. 初始化
        int j = 0;              // j为前缀末尾
        next[0] = 0;            // next[0] = 0
        for (int i = 1; i < n; i++) {   // i为后缀末尾

            // 3. 如果前后缀位置不匹配，则需要回退
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }

            // 4. 如果匹配则更新next数组
            if (pattern.charAt(i) == pattern.charAt(j)) {
                next[i] = ++j; // 注意要先 +1，因为next数组的含义如此
            }
        }
        return next;
    }

    public static boolean KMP(String text, String pattern) {
        int[] next = next(pattern);

        int j = 0;
        for (int i = 0; i < text.length(); ) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j > pattern.length() - 1) {
                    return true;
                }
            } else {
                if (j == 0) {
                    i++;
                } else {
                    j = next[j - 1];
                }
            }
        }
        return false;
    }
}
